#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 链表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 创建一个新的链表节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) { // 检查内存分配失败
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入数据到链表尾部
void insertNode(struct Node** head, struct Node** tail, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = *tail = newNode;  // 初始化链表
    }
    else {
        (*tail)->next = newNode;
        *tail = newNode;  // 更新尾部指针
    }
}

// 随机生成数据并插入链表
void generateRandomDataAndInsert(struct Node** head, struct Node** tail, int n) {
    for (int i = 0; i < n; i++) {
        int randNum = rand() % 100000;  // 随机生成0到99999之间的数
        insertNode(head, tail, randNum);
    }
}

// 遍历查找法
int linearSearch(struct Node* head, int target) {
    struct Node* current = head;
    int index = 0;

    // 遍历链表查找目标
    while (current != NULL) {
        if (current->data == target) {
            return index;  // 找到目标，返回其在链表中的位置
        }
        current = current->next;
        index++;
    }

    return -1;  // 未找到目标
}

// 释放链表内存
void freeList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    srand(time(0)); // 设置随机数种子

    // 数据量的不同设置
    int dataSizes[] = { 10000, 100000, 300000, 500000 };

    // 循环遍历不同数据量的测试
    for (int i = 0; i < 4; i++) {
        int n = dataSizes[i];
        struct Node* head = NULL;
        struct Node* tail = NULL;

        // 生成 n 个随机数据并插入链表
        generateRandomDataAndInsert(&head, &tail, n);
        printf("链表生成完毕，数据量: %d\n", n);

        // 获取用户输入的查找目标值
        int target;
        printf("请输入要查找的目标值：");
        scanf_s("%d", &target);

        // 开始记录查找时间
        clock_t startSearch = clock(); // 记录开始时间
        int result = linearSearch(head, target);
        clock_t endSearch = clock(); // 记录结束时间

        if (result != -1) {
            printf("找到了目标值: %d，位置: %d\n", target, result);
        }
        else {
            printf("没有找到目标值: %d\n", target);
        }

        // 计算查找耗时
        double searchTime = ((double)(endSearch - startSearch)) / CLOCKS_PER_SEC * 1000.0;  // 查找时间 (毫秒)
        printf("查找耗时: %.6f 毫秒\n", searchTime);

        // 释放内存
        freeList(head);
    }

    return 0;
}